{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make the XOR of All Segments Equal to Zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minChanges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使所有区间的异或结果为零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>​​​ 和一个整数 <code>k</code>​​​​​ 。区间 <code>[left, right]</code>（<code>left <= right</code>）的 <strong>异或结果</strong> 是对下标位于 <code>left</code> 和 <code>right</code>（包括 <code>left</code> 和 <code>right</code> ）之间所有元素进行 <code>XOR</code> 运算的结果：<code>nums[left] XOR nums[left+1] XOR ... XOR nums[right]</code> 。</p>\n",
    "\n",
    "<p>返回数组中 <strong>要更改的最小元素数</strong> ，以使所有长度为 <code>k</code> 的区间异或结果等于零。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,0,3,0], k = 1\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>将数组 [<strong>1</strong>,<strong>2</strong>,0,<strong>3</strong>,0] 修改为 [<strong>0</strong>,<strong>0</strong>,0,<strong>0</strong>,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,4,5,2,1,7,3,4,7], k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>将数组 [3,4,<strong>5</strong>,<strong>2</strong>,<strong>1</strong>,7,3,4,7] 修改为 [3,4,<strong>7</strong>,<strong>3</strong>,<strong>4</strong>,7,3,4,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,4,1,2,5,1,2,6], k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>将数组[1,2,<strong>4,</strong>1,2,<strong>5</strong>,1,2,<strong>6</strong>] 修改为 [1,2,<strong>3</strong>,1,2,<strong>3</strong>,1,2,<strong>3</strong>]</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= k <= nums.length <= 2000</code></li>\n",
    "\t<li><code>​​​​​​0 <= nums[i] < 2<sup>10</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-the-xor-of-all-segments-equal-to-zero](https://leetcode.cn/problems/make-the-xor-of-all-segments-equal-to-zero/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-the-xor-of-all-segments-equal-to-zero](https://leetcode.cn/problems/make-the-xor-of-all-segments-equal-to-zero/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,0,3,0]\\n1', '[3,4,5,2,1,7,3,4,7]\\n3', '[1,2,4,1,2,5,1,2,6]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n,m,mx=len(nums),2**10,3000\n",
    "        f = [mx] * m\n",
    "        for i in range(k):\n",
    "            mp=Counter()\n",
    "            cnt=0\n",
    "            for j in range(i,n,k):\n",
    "                cnt+=1\n",
    "                mp[nums[j]]+=1\n",
    "            g=[min(f)+cnt]*m\n",
    "            if i==0:\n",
    "                for j in range(0,m):g[j]=cnt-mp[j]\n",
    "            else:\n",
    "                for j in range(0,m):\n",
    "                    for x,c in mp.items():g[j]=min(g[j],f[j^x]+cnt-c)\n",
    "            f=g\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n,m=len(nums),2**10\n",
    "        f = [0] * m\n",
    "        for i in range(k):\n",
    "            mp=Counter()\n",
    "            cnt=0\n",
    "            for j in range(i,n,k):\n",
    "                cnt+=1\n",
    "                mp[nums[j]]+=1\n",
    "            g=[min(f)+cnt]*m\n",
    "            if i==0:\n",
    "                for j in range(0,m):g[j]=cnt-mp[j]\n",
    "            else:\n",
    "                for j in range(0,m):\n",
    "                    for x,c in mp.items():g[j]=min(g[j],f[j^x]+cnt-c)\n",
    "            f=g\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        MAXX = 2**10\n",
    "        \n",
    "        n = len(nums)\n",
    "        f = [float(\"inf\")] * MAXX\n",
    "        f[0] = 0\n",
    "        \n",
    "        for i in range(k):\n",
    "            count = Counter()\n",
    "            size = 0\n",
    "            for j in range(i, n, k):#遍历第i列，统计元素数量\n",
    "                count[nums[j]] += 1\n",
    "                size += 1\n",
    "\n",
    "            g = [min(f)+size] * MAXX    #最坏情况:前一列的最少操作数+这一列元素全换\n",
    "            for mask in range(MAXX):    #遍历目标[0,2^10)\n",
    "                for x, countx in count.items():\n",
    "                    g[mask] = min(g[mask], f[mask ^ x]+size - countx)   #记录最少操作数 \n",
    "            \n",
    "            f = g   #传递给f，供下一列使用\n",
    "\n",
    "        return f[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n,m=len(nums),2**10\n",
    "        f = [0] * m\n",
    "        for i in range(k):\n",
    "            mp=Counter()\n",
    "            cnt=0\n",
    "            for j in range(i,n,k):\n",
    "                cnt+=1\n",
    "                mp[nums[j]]+=1\n",
    "            g=[min(f)+cnt]*m\n",
    "            if i==0:\n",
    "                for j in range(0,m):g[j]=cnt-mp[j]\n",
    "            else:\n",
    "                for j in range(0,m):\n",
    "                    for x,c in mp.items():g[j]=min(g[j],f[j^x]+cnt-c)\n",
    "            f=g\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n,m,mx=len(nums),2**10,3000\n",
    "        f = [mx] * m\n",
    "        for i in range(k):\n",
    "            mp=Counter()\n",
    "            cnt=0\n",
    "            for j in range(i,n,k):\n",
    "                cnt+=1\n",
    "                mp[nums[j]]+=1\n",
    "            g=[min(f)+cnt]*m\n",
    "            if i==0:\n",
    "                for j in range(0,m):g[j]=cnt-mp[j]\n",
    "            else:\n",
    "                for j in range(0,m):\n",
    "                    for x,c in mp.items():g[j]=min(g[j],f[j^x]+cnt-c)\n",
    "            f=g\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        m = max(len(bin(num))-2 for num in nums)\n",
    "        pre = [inf]*(1<<m)\n",
    "        pre[0] = 0\n",
    "        tot = 0\n",
    "        for i in range(k):\n",
    "            lst = nums[i::k]\n",
    "            n = len(lst)\n",
    "            cnt = Counter(lst)\n",
    "            low = min(pre)\n",
    "            cur = [low+n for x in pre]\n",
    "            for j in range(1<<m):\n",
    "                for num in cnt:\n",
    "                    a, b = cur[j], pre[j ^ num] + n - cnt[num]\n",
    "                    cur[j] = a if a < b else b\n",
    "                    tot += 1\n",
    "            pre = cur[:]\n",
    "        print(tot)\n",
    "        return pre[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        m = max(len(bin(num))-2 for num in nums)\n",
    "        pre = [inf]*(1<<m)\n",
    "        pre[0] = 0\n",
    "        for i in range(k):\n",
    "            lst = nums[i::k]\n",
    "            n = len(lst)\n",
    "            cnt = Counter(lst)\n",
    "            low = min(pre)\n",
    "            cur = [low+n for x in pre]\n",
    "            for j in range(1<<m):\n",
    "                for num in cnt:\n",
    "                    a, b = cur[j], pre[j ^ num] + n - cnt[num]\n",
    "                    cur[j] = a if a < b else b\n",
    "            pre = cur[:]\n",
    "        return pre[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        # x 的范围为 [0, 2^10)\n",
    "        MAXX = 2**10\n",
    "        \n",
    "        n = len(nums)\n",
    "        f = [float(\"inf\")] * MAXX\n",
    "        # 边界条件 f(-1,0)=0\n",
    "        f[0] = 0\n",
    "        \n",
    "        for i in range(k):\n",
    "            # 第 i 个组的哈希映射\n",
    "            count = Counter()\n",
    "            size = 0\n",
    "            for j in range(i, n, k):\n",
    "                count[nums[j]] += 1\n",
    "                size += 1\n",
    "\n",
    "            # 求出 t2\n",
    "            t2min = min(f)\n",
    "\n",
    "            g = [t2min] * MAXX\n",
    "            for mask in range(MAXX):\n",
    "                # t1 则需要枚举 x 才能求出\n",
    "                for x, countx in count.items():\n",
    "                    g[mask] = min(g[mask], f[mask ^ x] - countx)\n",
    "            \n",
    "            # 别忘了加上 size\n",
    "            f = [val + size for val in g]\n",
    "\n",
    "        return f[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        # x 的范围为 [0, 2^10)\n",
    "        MAXX = 2**10\n",
    "        \n",
    "        n = len(nums)\n",
    "        f = [float(\"inf\")] * MAXX\n",
    "        # 边界条件 f(-1,0)=0\n",
    "        f[0] = 0\n",
    "        \n",
    "        for i in range(k):\n",
    "            # 第 i 个组的哈希映射\n",
    "            count = Counter()\n",
    "            size = 0\n",
    "            for j in range(i, n, k):\n",
    "                count[nums[j]] += 1\n",
    "                size += 1\n",
    "\n",
    "            # 求出 t2\n",
    "            t2min = min(f)\n",
    "\n",
    "            g = [t2min] * MAXX\n",
    "            for mask in range(MAXX):\n",
    "                # t1 则需要枚举 x 才能求出\n",
    "                for x, countx in count.items():\n",
    "                    g[mask] = min(g[mask], f[mask ^ x] - countx)\n",
    "            \n",
    "            # 别忘了加上 size\n",
    "            f = [val + size for val in g]\n",
    "\n",
    "        return f[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        clis, n = [Counter() for _ in range(k)], len(nums)\n",
    "        m = 1 << 10\n",
    "\n",
    "        for i in range(n):\n",
    "            clis[i%k][nums[i]] += 1\n",
    "        s = [0] + [float(\"-inf\")] * (m-1)\n",
    "        for p in range(k):\n",
    "            ss = [max(s)] * m\n",
    "            for i in range(m):\n",
    "                for j,v in clis[p].items():\n",
    "                    ss[i^j] = max(ss[i^j], s[i] + v)\n",
    "\n",
    "            s = ss\n",
    "        return n - s[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n, groups, size, dp = len(nums), [defaultdict(int) for _ in range(k)], [0] * k, [0] + [inf] * ((1 << 10) - 1)\n",
    "        for i in range(n):\n",
    "            groups[i % k][nums[i]] += 1\n",
    "            size[i % k] += 1\n",
    "        for i in range(k):\n",
    "            cur = [min(dp) + size[i]] * (1 << 10)\n",
    "            for j in range(1 << 10):\n",
    "                if dp[j] != inf:\n",
    "                    for k, v in groups[i].items():\n",
    "                        cur[k ^ j] = min(cur[k ^ j], dp[j] + size[i] - v)\n",
    "            dp = cur\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n,m,mx=len(nums),2**10,3000\n",
    "        f, g = [[mx] * m for i in range(k)], [mx] * k\n",
    "        for i in range(k):\n",
    "            mp=Counter()\n",
    "            cnt=0\n",
    "            for j in range(i,n,k):\n",
    "                cnt+=1\n",
    "                mp[nums[j]]+=1\n",
    "            if i==0:\n",
    "                for j in range(0,m):\n",
    "                    f[0][j]=cnt-mp[j]\n",
    "                    g[0]=min(g[0],f[0][j])\n",
    "            else:\n",
    "                for j in range(0,m):\n",
    "                    f[i][j]=g[i-1]+cnt\n",
    "                    for x,c in mp.items():\n",
    "                        f[i][j]=min(f[i][j],f[i-1][j^x]+cnt-c)\n",
    "                    g[i]=min(g[i],f[i][j])\n",
    "        return f[k-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n,m,mx=len(nums),2**10,3000\n",
    "        f, g = [[mx] * m for i in range(k)], [mx] * k\n",
    "        for i in range(k):\n",
    "            mp=Counter()\n",
    "            cnt=0\n",
    "            for j in range(i,n,k):\n",
    "                cnt+=1\n",
    "                mp[nums[j]]+=1\n",
    "            if i==0:\n",
    "                for j in range(0,m):\n",
    "                    f[0][j]=cnt-mp[j]\n",
    "                    g[0]=min(g[0],f[0][j])\n",
    "            else:\n",
    "                for j in range(0,m):\n",
    "                    f[i][j]=g[i-1]+cnt\n",
    "                    for x,c in mp.items():\n",
    "                        f[i][j]=min(f[i][j],f[i-1][j^x]+cnt-c)\n",
    "                    g[i]=min(g[i],f[i][j])\n",
    "        return f[k-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        N = max(nums).bit_length()\n",
    "        M = 1 << N\n",
    "        '''\n",
    "        26,19,19,\n",
    "        28,13,14,\n",
    "        6,25,28,\n",
    "        19,0,15,\n",
    "        25,11\n",
    "        要求: 1.每一列相同\n",
    "             2. 第一行异或为0\n",
    "        '''\n",
    "        \n",
    "        '''\n",
    "        f[i][state] 表示前i列(可以为0), 异或结果为state时最小改变数目\n",
    "        '''\n",
    "        f = [[inf] * (M) for _ in range(k+1)]\n",
    "        mins = [inf] * (k+1)\n",
    "        f[0][0] = 0 # 第0行数目都没有, 可以直接凑出0的state\n",
    "        mins[0] = 0\n",
    "        for i in range(1, k+1):\n",
    "            cnt = Counter(nums[i-1::k]) # 统计该列每个数字出现的个数, 如果要保留该数字就需要改变其他所有的数字\n",
    "            col = len(nums) // k + (len(nums) % k >= i) # 该列的数字总数目\n",
    "            for state in range(M): # 遍历上一列的所有状态\n",
    "                # 改变所有的数: 上一列最少状态和某个数异或得到state\n",
    "                f[i][state] = min(f[i][state], mins[i-1] + col) # 将第i列所有数字都改成state, 就可以异或为0\n",
    "                \n",
    "                # 尝试保留一个数字, 改变其他剩余的数字   \n",
    "                for num, count in cnt.items():\n",
    "                    f[i][state ^ num] = min(f[i][state ^ num], f[i-1][state] + col - count)\n",
    "            \n",
    "            mins[i] = min(f[i])\n",
    "                \n",
    "            \n",
    "        return f[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        MAX = 2 ** 10\n",
    "\n",
    "        dp = [[inf] * MAX for _ in range(k + 1)]\n",
    "        dp[k][0] = 0\n",
    "\n",
    "        for idx in range(k - 1, -1, -1):\n",
    "            cnts = defaultdict(int)\n",
    "            tot = 0\n",
    "            for i in range(idx, n, k):\n",
    "                x = nums[i]\n",
    "                cnts[x] += 1\n",
    "                tot += 1\n",
    "\n",
    "            min_prev = min(dp[idx + 1])\n",
    "            for mask in range(MAX):\n",
    "                dp[idx][mask] = min_prev + tot\n",
    "\n",
    "                for x, c in cnts.items():\n",
    "                    dp[idx][mask] = min(dp[idx][mask], dp[idx + 1][mask ^ x] + tot - c)\n",
    "\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter()\n",
    "        dic = defaultdict(Counter)\n",
    "        for i in range(n):\n",
    "            cnt[i % k] += 1\n",
    "            dic[i % k][nums[i]] += 1\n",
    "\n",
    "        dp = [[inf] * 1024 for _ in range(k + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, k + 1):\n",
    "            lo = min(dp[i - 1])\n",
    "            for j in range(1 << 10):\n",
    "                dp[i][j] = lo + cnt[i - 1]\n",
    "\n",
    "            for j in range(1 << 10):\n",
    "                for x, v in dic[i - 1].items():\n",
    "                    if dp[i - 1][j] == inf:\n",
    "                        continue\n",
    "                    dp[i][x ^ j] = min(dp[i][x ^ j], dp[i - 1][j] + cnt[i - 1] - v)\n",
    "\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter()\n",
    "        dic = defaultdict(Counter)\n",
    "        for i in range(n):\n",
    "            cnt[i % k] += 1\n",
    "            dic[i % k][nums[i]] += 1\n",
    "\n",
    "        dp = [[inf] * 1024 for _ in range(k + 1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1, k + 1):\n",
    "            lo = min(dp[i - 1])\n",
    "            for j in range(1 << 10):\n",
    "                dp[i][j] = lo + cnt[i - 1]\n",
    "\n",
    "            for j in range(1 << 10):\n",
    "                for x, v in dic[i - 1].items():\n",
    "                    dp[i][x ^ j] = min(dp[i][x ^ j], dp[i - 1][j] + cnt[i - 1] - v)\n",
    "\n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter()\n",
    "        dic = defaultdict(Counter)\n",
    "        for i in range(n):\n",
    "            cnt[i % k] += 1\n",
    "            dic[i % k][nums[i]] += 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx == k:\n",
    "                return [0] + [inf] * 1023\n",
    "            \n",
    "            t = dfs(idx + 1)\n",
    "            mi = min(t)\n",
    "            res = [mi + cnt[idx]] * 1024\n",
    "            for s in range(1024):\n",
    "                for x, v in dic[idx].items():\n",
    "                    res[x ^ s] = min(res[x ^ s], t[s] + cnt[idx] - v)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0)[0]\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, a: List[int], k: int) -> int:\n",
    "\n",
    "        # def min(a, b):\n",
    "        #     if a < b:\n",
    "        #         return a\n",
    "        #     return b\n",
    "\n",
    "        # def max(a, b):\n",
    "        #     if a > b:\n",
    "        #         return a\n",
    "        #     return b\n",
    "\n",
    "        ans=0\n",
    "        cnt = [[0] * 1024 for _ in range(k)]\n",
    "        n = len(a)\n",
    "        min_cnt = n\n",
    "        for i in range(k):\n",
    "            max_cnt = 0\n",
    "            for j in range(i, n, k):\n",
    "                cnt[i][a[j]] += 1\n",
    "                max_cnt = max(max_cnt, cnt[i][a[j]])\n",
    "            ans += max_cnt\n",
    "            min_cnt = min(min_cnt, max_cnt)\n",
    "        ans -= min_cnt\n",
    "\n",
    "        dp = [[-1] * 1024 for _ in range(k)]\n",
    "\n",
    "        def f(p, xor):\n",
    "            if p == 0:\n",
    "                return cnt[0][xor]\n",
    "            if dp[p][xor] >= 0:\n",
    "                return dp[p][xor]\n",
    "            res = 0\n",
    "            for i in range(p, n, k):\n",
    "                res = max(res, cnt[p][a[i]] + f(p-1, xor^a[i]))\n",
    "            dp[p][xor] = res\n",
    "            return res\n",
    "\n",
    "        return n - max(ans, f(k-1, 0))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minChanges(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return sum(num != 0 for num in nums)\n",
    "        cnt = Counter((i % k, num) for i, num in enumerate(nums))\n",
    "        each_div = [[] for _ in range(k)]\n",
    "        for (div, num), count in cnt.items():\n",
    "            each_div[div].append((num, count))\n",
    "        max_cnt = [max(each_div[div][j][1] for j in range(len(each_div[div]))) for div in range(k)]\n",
    "        result1 = len(nums) - sum(max_cnt) + min(max_cnt)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, acc_xor):\n",
    "            if i == -1 and acc_xor == 0:\n",
    "                return 0\n",
    "            elif i == -1:\n",
    "                return -inf\n",
    "            ans = -inf\n",
    "            for num, count in each_div[i]:\n",
    "                cur = count + dfs(i - 1, acc_xor ^ num)\n",
    "                ans = max(ans, cur)\n",
    "            return ans\n",
    "        \n",
    "        result2 = len(nums) - dfs(k - 1, 0)\n",
    "        return min(result1, result2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
